1. Field of the Invention
This disclosure relates to packet-switched communications systems. More particularly, this disclosure is directed to a system for queueing and selective pushout and method for use in packet communication processing modules.
2. Description of the Related Art
In the field of switched broadband integrated services digital networks (BISDN), packet processing such as asynchronous transfer mode (ATM) cell switching may be implemented using a shared-buffer-memory-based architecture, where incoming packets such as ATM cells destined for different output ports are buffered in queues sharing a common memory with the queues corresponding to those ports. Such packet processing is employed to support a wide spectrum of information services with very different bandwidth and quality of service (QoS) requirements.
A flexible way to provide different QoS is to use a priority mechanism inside a packet communications module. Priorities may be of two different types: delay (or time) priorities and loss (or space) priorities. Delay priorities provide preferential service to some classes of traffic in order to control their end-to-end delay and delay variation (jitter). Loss (or space) priorities provide preferential access to buffer space.
Pushout systems and methods allow the entire buffer space to be shared flexibly among the different queues as well as among the various space priority classes. As long as the buffer is not completely full, arriving packets of any priority are admitted. When the buffer is full, pushout systems provide space for the arriving packet by pushing out (i.e. overwriting) another packet that is already in buffer. In selective pushout, a packet that arrives to find the buffer full is allowed to enter by pushing out a packet of lower priority. For a packet communications module using first-in-first-out (FIFO) queues, while the physical memory location of the lower priority packet is usurped, the higher priority packet does not take over its position in its logical FIFO queue, i.e., the pushing and the pushed packets may be destined to different outputs and hence belong to different logical FIFO's. The higher priority packet that has arrived joins the tail of the logical FIFO queue for its own output.
Generally, the arriving packet has a choice of lower priority victims. In that case, the arriving packet should consider only those output queues containing packets of the lowest priority, and among these, the longest output queue should be selected. This bias against long queues allows shorter queues to lengthen, thereby creating a degree of fairness in the sharing of buffer space among output queues; it also tends to keep more memory outputs busy, which increases the efficiency of the system. Thus, pushout may be used to equalize queue lengths as well as to enforce space priorities (also referred to herein as loss priorities). If this longest queue has more than one lowest priority packet, the lowest priority packet nearest the head of the queue is selected for pushout. If a packet arrives to a full buffer when there are no lowest priority packets in the shared memory, then a packet of the second-lowest priority is pushed out. If there are no such packets, then the third-lowest priority is considered, and so on. If there are no packets in the buffer of priority lower than the arriving packet, then the arriving packet may push out a packet of the same priority as itself, from the longest queue containing such packets. While this does not immediately improve the packet loss rate for that priority class, it does contribute to queue length equalization. If all the packets in the buffer have higher priority than the arriving packet, then the arriving packet is dropped.
In a first implementation of selective pushout, the packets in the queue are in a FIFO linked-list arrangement, with the order of the FIFO queue provided by packet pointers, i.e., pointers for pointing from one packet to another. In addition to the QUEUE.sub.-- LENGTH (QL) counter and the FIRST.sub.-- PACKET (FP) and LAST.sub.-- PACKET (LP) pointers, the output queue also maintains FIRST.sub.-- PACKET.sub.-- OF.sub.-- CLASS.sub.-- i (FP[i]) pointers to the first packet of each priority class i. Whenever a pushout is needed, one of these pointers will indicate the packet to be pushed out. Then the queue must be scanned to update that pointer. In order to mend the FIFO linked-list after a pushout, the output queue also maintains another set of pointers PACKET.sub.-- BEFORE.sub.-- FIRST.sub.-- PACKET.sub.-- OF.sub.-- CLASS.sub.-- i (PBFP[i]) to the packet immediately preceding the first packet of each priority class i. This implementation of selective pushout is relatively simple and requires minimal state information, but in a worst case situation, the entire shared memory may need to be scanned in order to update the FP[i] pointer. For this reason, this first implementation is impractical for large buffer sizes.
In a second implementation of selective pushout shown in FIGS. 1A-1B, each output port maintains its FIFO queue as a doubly-linked-list, so that the FIFO order may be re-established whenever a packet is pushed out from the middle of the queue. In addition, each space priority class has its own singly-linked chain through the FIFO queue. These priority chains allow the ATM switch to quickly find the appropriate packet for a pushout.
As shown in FIG. 1A, every packet needs two pointers related to the FIFO order. In an exemplary embodiment for switching fixed length ATM packets (or cells), the two pointers are: a NEXT.sub.-- PACKET (NP) pointer and a PREVIOUS.sub.-- PACKET.sub.-- IN.sub.-- FIFO.sub.-- ORDER (PP) pointer. Each packet also needs one pointer related to its priority chain, which, in the above example, is the NEXT.sub.-- PACKET.sub.-- OF.sub.-- SAME.sub.-- CLASS (NS) pointer. In addition to the QUEUE.sub.-- LENGTH (QL) counter and the FIRST.sub.-- PACKET (FP) and LAST.sub.-- PACKET (LP) pointers, each output queue also needs two other pointers for each space priority class i=1, 2, . . . , P, in order to maintain the priority chains: a FIRST.sub.-- PACKET.sub.-- OF.sub.-- CLASS.sub.-- i (FP[i]) and a LAST.sub.-- PACKET.sub.-- OF.sub.-- CLASS.sub.-- i (LP[i]) pointer. As shown in FIG. 1B, when the packet occupying location X2 is pushed out by a newly arrived packet, the new packet joins the tail of the queue. The various pointers are then updated to re-establish the FIFO order after the pushout as shown in FIG. 1B. The second implementation of selective pushout thus uses more state information than the first implementation to provide for generally faster processing speeds, but the additional state information requires more space in the shared memory.